package Lee_code;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author blh
 * @date 2024年06月25日 15:45
 */
public class Lee_143_625 {
    public void reorderList(ListNode head) {
        // 记录头节点的位置
        ListNode record = head;
        ListNode start = head.next;
        // 统计一下有多少个需要排序的节点
        int nodeNum = 0;
        while (start != null) {
            nodeNum++;
            start = start.next;
        }
        // 记录节点
        Deque<ListNode> deque = new LinkedList<>();

        start = head.next;
        while (start != null) {
            deque.push(start);
            start = start.next;
        }
        while (!deque.isEmpty()){
            record.next = deque.pop();
            record = record.next;
            if (deque.isEmpty()){
                break;
            }
            record.next = deque.removeLast();
            record= record.next;
        }
    }
}
